package com.li.list;

public class 二叉搜索树转双向链表 {
	// 记录子树链表的最后一个节点，终结点只可能为只含左子树的非叶节点与叶节点
    protected static TreeNode leftLast = null;
	
	public static void main(String[] args) {
		TreeNode root  = new TreeNode(5);
		TreeNode TreeNode1 = new TreeNode(1);
		TreeNode TreeNode2 = new TreeNode(2);
		TreeNode TreeNode3 = new TreeNode(3);
		TreeNode TreeNode6 = new TreeNode(6);
		TreeNode TreeNode7 = new TreeNode(7);
		TreeNode TreeNode8 = new TreeNode(8);
		
		root.left = TreeNode3;
		TreeNode3.left = TreeNode1;
		TreeNode1.right = TreeNode2;
		
		root.right = TreeNode6;
		TreeNode6.right = TreeNode7;
		TreeNode7.right = TreeNode8;
		
		
		printList(convert(root));
	}
	
	/**
	 * 打印链表
	 * @param head
	 */
	public static void printList(TreeNode head){
		while(head!=null){
			System.out.print(head.val+" ");
			head = head.right;
		}
		System.out.println();
	}
	
    public static TreeNode convert(TreeNode root) {
        if(root==null)
            return null;
        if(root.left==null&&root.right==null){
            leftLast = root;// 最后的一个节点可能为最右侧的叶节点
            return root;
        }
        // 1.将左子树构造成双链表，并返回链表头节点
        TreeNode left = convert(root.left);
        // 3.如果左子树链表不为空的话，将当前root追加到左子树链表
        if(left!=null){
            leftLast.right = root;
            root.left = leftLast;
        }
        leftLast = root;// 当根节点只含左子树时，则该根节点为最后一个节点
        // 4.将右子树构造成双链表，并返回链表头节点
        TreeNode right = convert(root.right);
        // 5.如果右子树链表不为空的话，将该链表追加到root节点之后
        if(right!=null){
            right.left = root;
            root.right = right;
        }
        return left!=null?left:root;       
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
 
    }
 
}
